package cn.jdemo.algorithm.dynamicProgramming;

/**
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。
 * 一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费
 *
 * ---动规5步
 * 1.定义
 * dp[i] 爬到第i个台阶得最小花费
 * 2.递推公式
 *  // 注意这里为什么是加cost[i]，而不是cost[i-1],cost[i-2]之类的，因为题目中说了：每当你爬上一个阶梯你都要花费对应的体力值
 *  dp[i] = min(dp[i-1],dp[i-2]) + cost(i)
 * 3.初始化
 *  dp[0] = cost(i);
 *  dp[1] = cost(i);
 * 4.顺序遍历
 * 5.示例:{10,15,20}
 *          dp[i]
 *      0     10
 *      1     15
 *      2     30
 *  // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
 *  return min(dp[cost.size() - 1], dp[cost.size() - 2]);
 */
public class MinCostClimbingStairs {
    public static void main(String[] args) {
        // int[] cost= {1,100,1,1,1,100,1,1,100,1};
        int[] cost= {10,15,20};
        int res = new MinCostClimbingStairs().minCostClimbingStairs(cost);
        System.out.println(res);
    }
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        if (length == 1){
            return cost[0];
        }
        if (length == 2){
            return Math.min(cost[0],cost[1]);
        }
        int[] dp = new int[length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < length; i++) {
            dp[i] = cost[i] + Math.min(dp[i-1],dp[i-2]);
        }
        // [注意]最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return Math.min(dp[length - 1], dp[length - 2]);
    }
}
